package com.jiang.专题.动态规划.Q712;

/**
 * @author Jiang
 * @version 1.0
 * @date 2024/12/28 22:10
 */
class Solution {
    // 二维动态规划
//    public int minimumDeleteSum(String s1, String s2) {
//        int m = s1.length();
//        int n = s2.length();
//        int[][] dp = new int[m + 1][n + 1]; // dp[i][j]表示s1中索引0~i - 1的子字符串与s2中索引0~j - 1的子字符串，这两个子字符串的最小ASCII删除和
//
//        // 对dp进行初始化
//        for (int i = 1; i <= m; i++) {
//            dp[i][0] = s1.charAt(i - 1) + dp[i - 1][0];
//        }
//        for (int j = 1; j <= n; j++) {
//            dp[0][j] = s2.charAt(j - 1) + dp[0][j - 1];
//        }
//
//        // 计算两个子字符串最小ASCII删除和
//        for (int i = 1; i <= m; i++) {
//            char ci = s1.charAt(i - 1);
//            for (int j = 1; j <= n; j++) {
//                char cj = s2.charAt(j - 1);
//                if (ci == cj) {
//                    dp[i][j] = dp[i - 1][j - 1];
//                } else {
//                    dp[i][j] = Math.min(dp[i - 1][j] + ci, dp[i][j - 1] + cj);
//                }
//            }
//        }
//        return dp[m][n];
//    }

    // 一维动态规划
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[] dp = new int[n + 1]; // dp[j]表示s1中索引0~i - 1的子字符串与s2中索引0~j - 1的子字符串，这两个子字符串的最小ASCII删除和


        // 对dp进行初始化
        for (int j = 1; j <= n; j++) {
            dp[j] = s2.charAt(j - 1) + dp[j - 1];
        }

        // 计算两个子字符串最小ASCII删除和
        for (int i = 1; i <= m; i++) {
            char ci = s1.charAt(i - 1);
            int temp = dp[0]; // 保存dp[i-1][j-1]
            dp[0] += ci; // 更新dp[i][0]
            for (int j = 1; j <= n; j++) {
                char cj = s2.charAt(j - 1);
                int t = dp[j]; // 保存dp[i-1][j]
                if (ci == cj) {
                    dp[j] = temp; // 如果字符相等，dp[i][j] = dp[i-1][j-1]
                } else {
                    dp[j] = Math.min(dp[j - 1] + cj, dp[j] + ci); // 否则，dp[i][j] = min(dp[i][j-1] + s2[j-1]， dp[i-1][j] + s1[i-1],)
                }
                temp = t; // 更新temp为dp[i-1][j], 在下一次循环就是dp[i-1][j-1]
            }
        }
        return dp[n];
    }
}
